4.5 Генеративный подход к классификации

Как использовать распределение меток классов в задаче классификации. LDA, QDA и наивный байес

Классификационные модели, которые мы рассматривали в предыдущих параграфах, нацелены непосредственно на оценку P(YX)P(Y \vert X). Такие модели называются дискриминативными.

К ним относится, например, логистическая регрессия: она предлагает оценку P^(y=1x)=σ(wTˆx)\hat P(y=1 \vert x) = \sigma(w\^Tx). В процессе обучения дискриминативные модели подбирают разделяющую поверхность (гиперплоскость в случае логистической регрессии). Новые объекты дискриминативная модель классифицирует в зависимости от того, по какую сторону от разделяющей поверхности они лежат.

Например, обучившись на изображениях домашних кошек (y=0) и рысей (y=1), дискриминативная модель будет определять, новое изображение больше похоже на кошку или на рысь. При этом, если на вход такой модели дать изображение собаки (объект класса, которого не было в обучении, выброс), дискриминативная модель заведомо не сможет обнаружить, что это и не кошка, и не рысь, и отнесёт такой объект к одному из «знакомых» ей классов.

В этом параграфе мы поговорим о другой группе моделей, которые нацелены на оценку P(X,Y)=P(XY)P(Y)P(X, Y) = P(X \vert Y)P(Y). Такая модель описала бы, как обычно выглядят кошки, как они могут выглядеть, а каких кошек точно не бывает. Так же она описала бы и рысей. Она также определила бы по обучающим данным, насколько изображения кошек встречаются чаще, чем изображения рысей, т.е. оценила бы P(Y)P(Y).

Генеративный и дискриминативный подходы к обучению

Если модель позволила точно оценить распределение P(XY)P(X \vert Y), с её помощью можно генерировать объекты из этого условного распределения, в нашем примере — изображения кошек и рысей соответственно.

А вместе распределение P(X,Y)P(X, Y) дало бы нам возможность генерировать изображения и кошек, и рысей, причём именно в той пропорции, в которой они встречаются в реальном мире. Поэтому модели, оценивающие P(X,Y)P(X, Y), называют генеративными. Ещё одно достоинство генеративных моделей — их способность находить выбросы в данных: объект xx можно считать выбросом, если P(xy)P(x \vert y) мало для каждого класса yy.

Заметим, что находить выбросы с помощью генеративной модели можно и когда класс всего один — то есть никакие метки классов не доступны. Такая задача называется одноклассовой классификацией. Например, если у нас есть не размеченный датасет с аудиозаписями речи людей, то, обучив на нём генеративную модель, оценивающую в данном случае P(XY)=P(X)P(X \vert Y)=P(X), мы сможем для нового аудио xx определить, похоже ли оно на аудиозапись человеческой речи (значение P(x)P(x) велико), или это что-то другое: синтезированная речь, посторонний шум и т.п. (значение P(x)P(x) мало).

Если мы знаем, что «выбросы», с которыми модели предстоит сталкиваться, — это, как правило, синтезированная речь, то, мы можем дополнить датасет вторым классом, состоящим из синтезированной речи, и смоделировать также распределение этого класса. Это позволит существенно увеличить качество детектирования таких выбросов.

Чтобы использовать генеративную модель для классификации, необходимо выразить P(YX)P(Y \vert X) через P(XY)P(X \vert Y) и P(Y)P(Y). Сделать это позволяет формула Байеса:

P(yx)=P(x,y)yYP(y)P(xy)=P(y)P(xy)yYP(y)P(xy)P(y \vert x) = \frac{P(x, y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')}

Классификация в генеративных моделях осуществляется с помощью байесовского классификатора:

a(x)=argmaxyYP(yx)=argmaxyYP(y)P(xy)yYP(y)P(xy)=argmaxyYP(y)P(xy)a(x) = \arg\max\limits_{y\in Y} P(y \vert x) = \arg\max\limits_{y\in Y} \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \arg\max\limits_{y\in Y} P(y)P(x \vert y)

Оценить P(Y)P(Y), как правило, несложно. Для этого используют частотные оценки, полученные в обучающей выборке:

Выражение (1)

P^(Y=y)=#(Y=y)N\hat P(Y=y) = \frac{\#(Y=y)}{N}

Отметим ещё раз, что использование генеративного подхода позволяет внедрять в модель априорные знания о P(y)P(y). Это не очень впечатляет, когда речь идёт о бинарной классификации, но всё меняется, если рассмотреть задачу ASR (автоматического распознавания речи), в которой по записи голоса восстанавливается произносимый текст.

Таргетами здесь могут быть любые предложения или даже более развёрнутые тексты. При этом размеченных данных (запись, текст) обычно намного меньше, чем доступных текстов, и обученная на большом чисто текстовом корпусе языковая модель, которая будет оценивать вероятность того или иного предложения, может стать большим подспорьем, позволив из нескольких фонетически корректных наборов слов выбрать тот, который в большей степени похож на настоящее предложение.

Но как смоделировать распределение P(X,Y)P(X, Y)? Пространство всех возможных функций распределения P(X,Y)P(X, Y) бесконечномерно, из-за чего оценить произвольное распределение с помощью конечной выборки невозможно. Поэтому перед оценкой P(X,Y)P(X, Y) на это распределение накладывают дополнительные ограничения. Некоторые простые примеры таких ограничений мы рассмотрим в следующих разделах.

Gaussian discriminant analysis

Модель гауссовского (или квадратичного) дискриминантного анализа (GDA) строится в предположении, что распределение объектов каждого класса yy подчиняется многомерному нормальному закону со средним μy\mu_y и ковариационной матрицей Σy\Sigma_y:

p(xy)=1(2π)n/2Σy1/2exp(12(xμy)TΣy1(xμy))p(x \mid y)=\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_y\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x-\mu_y\right)^T \Sigma_y^{-1}\left(x-\mu_y\right)\right)

Тогда функция правдоподобия

L(P(Y),μ,Σ)=i=1Np(xiyi;μyi,Σyi)P(yi)\mathcal L(P(Y), \mu, \Sigma) = \prod_{i=1}^N p(x_i \vert y_i; \mu_{y_i}, \Sigma_{y_i})P(y_i)

достигает максимума при

μ^y=i=1Nxi1yi=yi=1N1yi=y,Σ^y=i=1N(xiμ^y)(xiμ^y)T1yi=yi=1N1yi=y\hat\mu_y = \frac{\sum\limits_{i=1}^N{x_i\mathbb{1}_{y_i=y}}}{\sum\limits_{i=1}^N\mathbb{1}_{y_i=y}},\hspace{5mm} \hat\Sigma_y = \frac{\sum\limits_{i=1}^N{(x_i - \hat\mu_{y})(x_i - \hat\mu_{y})^T \mathbb{1}_{y_i=y}}}{\sum\limits_{i=1}^N\mathbb{1}_{y_i=y}}

И P^(Y)\hat P(Y), представленной выше см. выражение (1)(1).

Рассмотрим, как выглядит разделяющая поверхность в модели GDA. На поверхности, разделяющей классы yiy_i и yjy_j выполняется

P(yix)=P(yjx)P(y_i \vert x)=P(y_j \vert x) \Leftrightarrow

p(xyi)P(yi)=p(xyj)P(yj)p(x \vert y_i)P(y_i) = p(x \vert y_j)P(y_j)\Leftrightarrow

logp(xyi)+logP(yi)logp(xyj)logP(yj)=0\log p(x \vert y_i) + \log P(y_i) - \log p(x \vert y_j) - \log P(y_j) = 0\Leftrightarrow

Выражение (2)

12(xμyi)TΣyi1(xμyi)log(2π)n/2Σyi1/2+logP(yi)+12(xμyj)TΣyj1(xμyj)+log(2π)n/2Σyj1/2logP(yj)=0 \begin{equation} -\frac{1}{2}(x-\mu_{y_i})^T\Sigma_{y_i}^{-1} (x-\mu_{y_i})-\log (2\pi)^{n/2}|\Sigma_{y_i}|^{1/2} + \log P(y_i) + \frac{1}{2}(x-\mu_{y_j})^T\Sigma_{y_j}^{-1} (x-\mu_{y_j}) + \log (2\pi)^{n/2}|\Sigma_{y_j}|^{1/2} - \log P(y_j) = 0 \end{equation}

Поскольку левая часть уравнения (2) квадратична по xx, разделяющая поверхность между двумя классами будет представлять из себя гиперповерхность порядка 2. Пример разделяющей поверхности многоклассовой модели GDA приведён на рис.

13

Плотность классов и разделяющая поверхность в многоклассовой модели LDA см. рисунок.

13

Linear Discriminant Analysis

В выражении (2) член второго порядка xT(Σyj1Σyi1)xx^T (\Sigma_{y_j}^{-1} - \Sigma_{y_i}^{-1})x зануляется при Σyi=Σyj\Sigma_{y_i}=\Sigma_{y_j}. Таким образом, если дополнительно предположить, что все классы имеют общую ковариационную матрицу Σ\Sigma, разделяющая поверхность между любыми двумя классами будет линейной (см. рисунок). Поэтому такая модель называется линейным дискриминантным анализом (LDA).

На этапе обучения единственное отличие модели LDA от GDA состоит в оценке ковариационной матрицы:

Σ^=1Ni=1N(xiμ^yi)(xiμ^yi)T\hat \Sigma = \frac{1}{N}\sum\limits_{i=1}^N{(x_i - \hat\mu_{y_i})(x_i - \hat\mu_{y_i})^T}

Заметим, что в модели GDA для каждого класса требовалось оценить порядка d2d^2 параметров. Это может привести к переобучению в случае, если размерность пространства признаков велика, а некоторые классы представлены в обучающей выборке малым количеством объектов. В LDA для каждого класса требуется оценить лишь порядка dd параметров (значение P(y)P(y) и элементы вектора μy\mu_y), и ещё d2d^2 общих для всех классов параметров (элементы матрицы Σ\Sigma).

Таким образом, основное преимущество модели LDA перед GDA — её меньшая склонность к переобучению, недостаток — линейная разделяющая поверхность.

Метод наивного байеса

Предположим, что признаки XX объектов каждого класса yy — независимые случайные величины:

yYU,V:UV={1,...d},xuRU,xvRV\forall y\in Y \hspace{2mm} \forall U, V: U\sqcup V = \{1, ... d\}, \hspace{2mm} \forall x^u\subset \mathbb R^{|U|}, x^v\subset \mathbb R^{|V|}

P(XUxu,XVxvY=y)=P(XUxuY=y)P(XVxuY=y).P(X^U\in x^u, X^V\in x^v|Y=y) = P(X^U\in x^u|Y=y)P(X^V\in x^u|Y=y).

В таком случае говорят, что величины XX условно независимы относительно YY. Тогда справедливо

Выражение (3)

P(XY)=P(X1,X2,...,XdY)=P(X1Y)P(X2,...,XdY)=...=P(X1Y)P(X2Y)...P(XdY)\begin{equation} P(X \vert Y) = P(X^1, X^2, ..., X^d \vert Y) = P(X^1 \vert Y)P(X^2, ..., X^d \vert Y) = ... = P(X^1 \vert Y)P(X^2 \vert Y)...P(X^d \vert Y) \end{equation}

То есть для того, чтобы оценить плотность многомерного распределения P(XY)P(X \vert Y) достаточно оценить плотности одномерных распределений P(XiY)P(X^i \vert Y), см. рисунок.

13

На рисунке приведён пример условно независимых относительно YY случайных величин X1,X2X^1, X^2. Для оценки плотности двумерных распределений объектов классов достаточно оценить плотности маргинальных распределений, изображённые графиками вдоль осей.

Рассмотрим пример. Пусть решается задача классификации отзывов об интернет-магазине на 2 категории: Y=0Y=0 — отрицательный отзыв, клиент остался не доволен, и Y=1Y=1 — положительный отзыв. Пусть признак XwX^w равен 1, если слово ww присутствует в отзыве, и 0 иначе. Тогда условие выражения (3)(3) означает, что, в частности, наличие или отсутствие слова «дозвониться» в отрицательном отзыве не влияет на вероятность наличия в этом отзыве слова «телефон».

На практике в процессе feature engineering почти всегда создаётся много похожих признаков, и условно независимые признаки можно встретить очень редко. Поэтому генеративную модель, построенную в предположении условия выражения (3)(3), называют наивным байесовским классификатором (Naive Bayes classifier, NB).

Обучение модели NB заключается в оценке распределений P(Y)P(Y) и P(XiY)P(X^i \vert Y). Для P(Y)P(Y) можно использовать частотную оценку выражения (1)(1). P(Xiy)P(X^i \vert y) — одномерное распределение. Рассмотрим несколько способов оценки одномерного распределения.

Оценка одномерного распределения

Пусть мы хотим оценить одномерное распределение P(X)P(X).

Если распределение P(X)P(X) дискретное, требуется оценить его функцию массы, то есть вероятность того, что величина XX примет значение xjx_j. Метод максимума правдоподобия приводит к частотной оценке:

Выражение (4)

P^(X=xj)=#(X=xj)N\hat P(X = x_j) = \frac{\#(X = x_j)}{N}

Где NN — размер выборки, по которой оценивается распределение XX (количество объектов класса yy в случае оценки плотности класса yy).

При этом может оказаться, что некоторое значение xjx_j ни разу не встречается в обучающей выборке. Например, в случае классификации отзывов методом Наивного Байеса, слово «амбивалентно» не встретилось ни в одном положительном отзыве, но встретилось в отрицательных. Тогда использование оценки выражения (4)(4) приведёт к тому, что все отзывы с этим словом будут определяться NB как отрицательные с вероятностью 1. Чтобы избежать принятия таких радикальных решений при недостатке статистики, используют сглаживание Лапласа:

P^(X=xj)=#(X=xj)+αN+mα,\hat P(X = x_j) = \frac{\#(X = x_j) + \alpha}{N + m\alpha},

где mm — количество различных значений, принимаемых случайной величиной XX, α\alpha — гиперпараметр.

Для оценки плотности pp абсолютно непрерывного распределения в точке aa можно разделить количество объектов обучающей выборки в окрестности точки aa на размер этой окрестности:

p^(a)=j1ah<Xj<a+h2h=j1h<Xja<h2h.\hat p(a) = \frac{\sum\limits_{j}\mathbb{1}_{a - h < X_j < a + h}}{2h} = \frac{\sum\limits_{j}\mathbb{1}_{-h < X_j - a < h}}{2h}.

Обычно объекты, лежащие дальше от точки aa, учитывают с меньшим весом. Таким образом, оценка плотности приобретает вид

p^(a)=jKh(Xja)2h,\hat p(a) = \frac{\sum\limits_{j}K_h(X_j - a)}{2h},

где функция KhK_h, называемая ядром, обычно имеет носитель (h,h)(-h, h) (см. рисунок ниже). Такой способ оценки плотности называют непараметрическим.

13

Результат оценки плотности с разными ядрами. Использованы изображения из:

13

При параметрической оценке плотности предполагают, что искомое распределение лежит в параметризованном классе, и подбирают значения параметров при помощи метода максимума правдоподобия. Например, предположим, что искомое распределение нормальное. Тогда функция его плотности имеет вид

p(x)=1σ2πexp((xμ)22σ2)p(x) = \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)

Таким образом, чтобы оценить плотность p(x)p(x), достаточно оценить параметры μ,σ\mu, \sigma. Метод максимума правдоподобия в этом случае даст такие оценки:

μ^=X\hat\mu = \overline X — выборочное среднее, σ^=1Nj=1N(XjX)\hat\sigma = \sqrt{\frac{1}{N}\sum_{j=1}^N (X_j - \overline X)} — выборочное стандартное отклонение.

Если в модели NB распределения всех признаков объектов каждого класса нормальные, оценив параметры этих распределений, мы сможем каждый класс yy описать нормальным распределением со средним μp\mu_p и диагональной ковариационной матрицей, значения на диагонали которой обозначим σp\sigma_p.

Таким образом, полученная модель (Gaussian Naive Bayes, GNB) эквивалентна модели GDA с дополнительным ограничением на диагональность ковариационных матриц.

Наивный байесовский подход и логистическая регрессия

Предположим теперь, что в модели GNB класса всего 2, причём соответствующие им ковариационные матрицы совпадают, как это было в модели LDA. Таким образом σ0=σ1=σ\sigma_0 = \sigma_1 = \sigma.

Посмотрим, как будет выглядеть P(YX)P(Y \vert X) в этом случае. По теореме Байеса имеем

P(Y=1X)=P(Y=1)P(XY=1)P(Y=1)P(XY=1)+P(Y=0)P(XY=0)P(Y=1 \vert X) = \frac{P(Y = 1)P(X \vert Y = 1)}{P(Y = 1)P(X \vert Y = 1) + P(Y = 0)P(X \vert Y = 0)}

Разделим числитель и знаменатель полученного выражения на числитель:

P(Y=1X)=11+P(Y=0)P(XY=0)P(Y=1)P(XY=1)=11+exp(lnP(Y=0)P(XY=0)P(Y=1)P(XY=1))P(Y=1 \vert X) = \frac{1}{1 + \frac{P(Y = 0)P(X \vert Y = 0)}{P(Y = 1)P(X \vert Y = 1)}} = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)P(X \vert Y=0)}{P(Y=1)P(X \vert Y=1)}\right)}

Из условной независимости XiX^i относительно YY получаем

Формула (5)

P(Y=1X)=11+exp(lnP(Y=0)P(Y=1)+i=1dlnP(XiY=0)P(XiY=1))\begin{equation} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)}\right)} \end{equation}

Перепишем сумму в знаменателе, воспользовавшись формулой плотности нормального распределения

i=1dlnP(XiY=0)P(XiY=1)=i=1dln12πσi2exp((Xiμ0,i)22σi2)12πσi2exp((Xiμ1,i)22σi2)\sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)} = \sum\limits_{i=1}^d \ln\frac{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{0,i})^2}{2\sigma_i^2}\right)}{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{1,i})^2}{2\sigma_i^2}\right)}

=i=1d(Xiμ1,i)2(Xiμ0,i)22σi2=i=1d(μ0,iμ1,iσi2Xi+μ1,i2μ0,i22σi2)= \sum\limits_{i=1}^d \frac{\left(X^i - \mu_{1, i}\right)^2 - \left(X^i - \mu_{0, i}\right)^2}{2\sigma_i^2}= \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)

Подставляя это выражение в формулу (5) , получаем

P(Y=1X)=11+exp(lnP(Y=0)P(Y=1)+i=1d(μ0,iμ1,iσi2Xi+μ1,i2μ0,i22σi2))P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)\right)}

Таким образом, P(Y=1X)P(Y=1 \vert X) представляется в GNB с общей ковариационной матрицей в таком же виде, как в модели логистической регрессии:

Формула (6)

P(Y=1X)=11+exp(w0+i=1dwiXi)\begin{equation} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(w_0 + \sum\limits_{i=1}^d w_i X^i\right)} \end{equation}

где в случае GNB

w0=lnP(Y=1)P(Y=0)+i=1dμ1,i2μ0,i22σi2,wi=μ0,iμ1,iσi2i=1,,lw_0 = \ln\frac{P(Y=1)}{P(Y=0)} +\sum\limits_{i=1}^d\frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}, \quad w_i = \frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2} \hspace{1cm} i=1, \dots, l

Однако это не значит, что модели эквивалентны: модель логистической регрессии накладывает менее строгие ограничения на распределение P(X,Y)P(X, Y), чем GNB.

Так, XiX^i могут не являться условно независимыми относительно YY, а распределения P(XY=y)P(X \vert Y=y) могут не удовлетворять нормальному закону, но P(yX)P(y \vert X) может при этом всё равно представляться в виде формулы (6) .

В этом случае использование метода логистической регрессии предпочтительнее. С другой стороны, если есть основания полагать, что требования GNB выполняются, то от GNB можно ожидать более высокого качества классификации по сравнению с логистической регрессией.

Чтобы добавить в заметки выделенный текст, нажмите Command + E
Предыдущий параграф4.4. Как оценивать вероятности

Как правильно оценить вероятности классов в задаче классификации

Следующий параграф4.6. Байесовский подход к оцениванию

Байесовская статистика. Априорные и апостериорные распределения на параметры моделей. MAP-оценки. Байесовский подход к выбору моделей. Байесовский подход для задачи линейной регресии

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.